// stlhelper.h : helper functions and macros
//
/////////////////////////////////////////////////////////////////////////////

#if !defined(STLHELPER_H)
#define STLHELPER_H

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <algorithm>
#include <functional>
#include <vector>
#include <deque>

#ifdef _MY_STL_MACROS
#define beg_to_end(container) (container).begin(),(container).end()
#define for_iter(container, iter_type, iter) \
   for(iter_type iter = (container).begin(); \
      iter != (container).end(); ++iter)
#endif

/*
		count_removed_duplicates
		remove_duplicates
		includes
		includes
		copy_if
		for_each_if
		erase_if_found
		min_max_element
		set_mark_union
		set_mark_diff
		mark_consecutive_duplicates
		op_ignore
*/

/*****************************************************************************************
	for_each_pair
	
	
		  Apply a function to every element of a pair of ranges.
*****************************************************************************************/
template<typename _InputIter1, typename _InputIter2, typename _Function>
inline _Function
for_each_pair(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _Function __f)
{
	for ( ; __first1 != __last1; ++__first1, ++__first2)
		__f(*__first1, *__first2);
	return __f;
}
	
/*****************************************************************************************
	for_each_iterpair_stride
	
	
		  Apply a function to iterators pointing to every nth elements of a pair of ranges
*****************************************************************************************/
template<typename _RandomAccessIter1, typename _RandomAccessIter2, typename _Function>
inline _Function
for_each_iterpair_stride(_RandomAccessIter1 __first1, _RandomAccessIter1 __last1,
					_RandomAccessIter2 __first2, unsigned stride, _Function __f)
{
	for ( ; __first1 < __last1; __first1+=stride, first2+=stride)
		__f(__first1, __first2);
	return __f;
}
	



/*****************************************************************************************
	str_search_and_replace
	
		  Search for all instance of a string and replace with another
*****************************************************************************************/
inline void str_search_and_replace(std::string& str, const std::string& str_find, const std::string& replace)
{
	unsigned find_len = str_find.length();
	std::string::size_type pos = str.find(str_find);
	while (pos != std::string::npos)
	{
		str.replace(pos, find_len, replace);
		pos = str.find(str_find);
	}
}
	


/*****************************************************************************************
						find_pos_in_vector
******************************************************************************************/
template <typename T>
inline unsigned find_pos_in_vector(std::vector<T>& vec, T t)
{
	return (std::find(vec.begin(), vec.end(), t) - vec.begin());
}

/*****************************************************************************************
						vector_release_mem
******************************************************************************************/
template<typename t> void vector_release_mem(std::vector<t>& vec)
{
	std::vector<t>().swap(vec);
}


/*****************************************************************************************
						deque_release_mem
******************************************************************************************/
template<typename t> void deque_release_mem(std::deque<t>& dec)
{
	std::deque<t>().swap(dec);
}


/*****************************************************************************************
						is_sorted
						
original source from sgi
include here only to ensure that it is always present

template <typename It, typename PRED>
bool is_sorted(It b, It e, PRED pred)
{
	return std::adjacent_find(b, e, std::not2(pred)) == e;}
******************************************************************************************/
namespace stlhelper
{
template<typename _ForwardIter, typename _StrictWeakOrdering>
    bool
    is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp)
    {

      if (__first == __last)
	return true;

      _ForwardIter __next = __first;
      for (++__next; __next != __last; __first = __next, ++__next) {
	if (__comp(*__next, *__first))
	  return false;
      }

      return true;
    }

	template<typename _ForwardIter>
    bool
    is_sorted(_ForwardIter __first, _ForwardIter __last)
    {

      if (__first == __last)
		  return true;

      _ForwardIter __next = __first;
      for (++__next; __next != __last; __first = __next, ++__next)
	  {
		  if (*__next < *__first)
			  return false;
      }

      return true;
    }

}


/*****************************************************************************************
						is_unique
******************************************************************************************/
namespace stlhelper
{
	template<typename _ForwardIter, typename _StrictWeakOrdering>
    bool is_unique(_ForwardIter first, _ForwardIter last, _StrictWeakOrdering comp)
    {
		return adjacent_find(first, last, comp) == last;
    }
	template<typename _ForwardIter>
    bool is_unique(_ForwardIter first, _ForwardIter last)
    {
		return adjacent_find(first, last) == last;
    }
}
/*****************************************************************************************
						transform_if
******************************************************************************************/
template <typename InputIterator, typename OutputIterator, typename UnaryOp>
inline OutputIterator transform_if(InputIterator first, InputIterator last,	
									OutputIterator result, UnaryOp op)
{
    for (; first != last; ++first)
		if (*result = op(*first))
			++result;
    return result;
}


template <typename InputIterator, typename OutputIterator, typename UnaryOp, typename UnaryPred>
inline OutputIterator transform_if(InputIterator first, InputIterator last,	
									OutputIterator result, UnaryOp op, UnaryPred pred)
{
    for (; first != last; ++first)
	{
		if (pred(*first))
		{
			*result = op(*first);
			++result;
		}
	}
    return result;
}

template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOp, class BinaryPred>
inline OutputIterator transform_if(InputIterator1 first1, InputIterator1 last1,
				InputIterator2 first2, OutputIterator result,
				BinaryOp binary_op, BinaryPred pred)
{
    for (; first1 != last1; ++first1, ++first2)
	{
		if (pred(*first, *first2))
		{
			*result = binary_op(*first1, *first2);
			++result;
		}
	}
    return result;
}

/*****************************************************************************************
						compact_vector
******************************************************************************************/
template <typename T>
inline void compact_vector(std::vector<T>& c)
{
	std::vector<T>(c).swap(c);
}

/*****************************************************************************************
						count_removed_duplicates
******************************************************************************************/
template <typename Container>
unsigned count_removed_duplicates(Container& c)
{
	typename Container::iterator i = std::unique(c.begin(), c.end());
	unsigned cnt = std::distance(i, c.end());
	c.erase(i, c.end());	
	return cnt;
}


template <class Container, class pred>
unsigned count_removed_duplicates(Container& c, pred p)
{
	typename Container::iterator i = std::unique(c.begin(),c.end(), p);
	unsigned cnt = std::distance(i, c.end());
	c.erase(i, c.end());	
	return cnt;
}

/*****************************************************************************************
						remove_duplicates
******************************************************************************************/
template <class Container>
void remove_duplicates(Container& c)
{
	c.erase(std::unique(c.begin(),c.end()), c.end());	
}


template <typename Container, typename pred>
void remove_duplicates(Container& c, pred p)
{
	c.erase(std::unique(c.begin(),c.end(), p), c.end());
}

/*****************************************************************************************
						remove_specified_duplicates
******************************************************************************************/
template<typename T>
struct op_eq_specified
{
	T specified;
	op_eq_specified(T specified_) : specified(specified_){}
	bool operator()(const T& a, const T& b)
	{ return a == b && a == specified; }
};
	

template <typename  Container, typename T>
Container& remove_specified_duplicates(Container& c, T t)
{
	typename Container::iterator first_unique =
		std::unique(c.begin(), c.end(), op_eq_specified<T>(t));
	if (first_unique != c.end())
		c.erase(first_unique, c.end());
	return c;
}



/*****************************************************************************************
						includes
******************************************************************************************/
template<class InputIterator, class Predicate>
bool includes_if(InputIterator first, InputIterator last,
                      Predicate pred)
{
	return std::find_if(first, last, pred) != last;
}


template< class Container, class Predicate>
inline bool includes_if(Container& c, Predicate pred)
{
	return includes(c.begin(), c.end(), pred);
}

template<class InputIterator, class T>
bool includes(InputIterator first, InputIterator last, T val)
{
	return std::find(first, last, val) != last;
}


template< class Container, class T>
inline bool includes(Container& c, T val)
{
	return includes(c.begin(),c.end(), val);
}

/*****************************************************************************************
						copy_if
******************************************************************************************/
template<class InIt, class OutIt, class PRED> inline
unsigned copy_if(InIt i, InIt last, OutIt dest, PRED pred)
{
	unsigned cnt = 0;
	for (; i != last; ++i)
		if (pred(*i))
		{
			*dest++ = *i;
			++cnt;
		}
	return (cnt);
}

/*****************************************************************************************
						for_each_if
******************************************************************************************/
template<typename InIt, typename Fn, typename Pred> inline
Fn for_each_if(InIt i, InIt last, Fn op, Pred pred)
{
	for (; i != last; ++i)
		if (pred(*i))
			op(*i);
	return op;
}


/*****************************************************************************************
						erase_if_found
******************************************************************************************/
template< class Container, class iterator, class T>
inline void erase_if_found(Container& c, iterator start, iterator end, T t)
{
	iterator f = find(start, end, t);
	if (f != end)
		c.erase(f);
}


template< class Container, class T>
inline void erase_if_found(Container& c, T t)
{
	typename Container::iterator f = find(c.begin(),c.end(), t);
	if (f != c.end())
		c.erase(f);
}


/*****************************************************************************************
						min_max_element
******************************************************************************************/
template <class it> std::pair<it, it>
min_max_element (it first, it last)
{
    if (first == last)
		return(std::pair<it, it>(first, first));
	
    it minResult = first;
    it maxResult = first;

	// have two iterators which point to successive elements
    it second	  = first;
	++second;

	// compare two successive iterators to each other first and save one compare every
	// two elements
    while (second != last)
    {
		if (*first < *second)
		{
			if (*first < *minResult)
				minResult = first;
			if (*maxResult < *second)
				maxResult = second;
		}
		else if (*second < *first)
		{
			if (*maxResult < *first)
				maxResult = first;
			if (*second < *minResult)
				minResult = second;
		}
		++first;
		++second;		
    }
	
	// handle odd number of elements
	if (first != last)
	{
		if (*first < *minResult)
			minResult = first;
		if (*maxResult < *first)
			maxResult = first;
	}
	return std::pair<it, it>(minResult, maxResult);
}

template <class it, class LessCompare> std::pair<it, it>
min_max_element (it first, it last, LessCompare comp)
{
    if (first == last)
		return std::pair<it, it> (first, first);
	
    it minResult = first;
    it maxResult = first;

	// have two iterators which point to successive elements
    it second	  = first;
	++second;

	// compare two successive iterators to each other first and save one compare every
	// two elements
    while (second != last)
    {
		if (comp(*first < *second))
		{
			if (comp(*first, *minResult))
				minResult = first;
			if (comp(*maxResult, *second))
				maxResult = second;
		}
		else if (comp(*second, *first))
		{
			if (comp(*maxResult, *first))
				maxResult = first;
			if (comp(*second, *minResult))
				minResult = second;
		}
		++first;
		++second;		
    }
	
	// handle odd number of elements
	if (first != last)
	{
		if (comp(*first, *minResult))
			minResult = first;
		if (comp(*maxResult, *first))
			maxResult = first;
	}

	return std::pair<it, it>(minResult, maxResult);
}

/*****************************************************************************************
						set_mark_union
******************************************************************************************/
template<class _InIt1, class _InIt2, class PRED_Less, class PRED_Mark>
inline
void set_mark_union(_InIt1 i1, _InIt1 last1,
					 _InIt2 i2, _InIt2 last2,
					 PRED_Less pred_less,
					 PRED_Mark pred_mark)
{
	if (i1 == last1 || i2 == last2)
		return;
	
	for (;;)
	{
		if (pred_less(*i1, *i2))
		{
			if (++i1 == last1)
				break;
		}
		else if (pred_less(*i2, *i1))
		{
			if (++i2 == last2)
				break;
		}
		else
		{
			pred_mark(*i1, *i2);
			if (++i1 == last1 || ++i2 == last2)
				break;
		}
	}
}



/*****************************************************************************************
						set_mark_diff
******************************************************************************************/
template<class _InIt1, class _InIt2, class PRED_Less, class PRED_Mark1, class PRED_Mark2>
inline
void set_mark_diff(_InIt1 i1, _InIt1 last1,
					 _InIt2 i2, _InIt2 last2,
					 PRED_Less pred_less,
					 PRED_Mark1 pred_mark1,
					 PRED_Mark2 pred_mark2)
{
	if (i1 == last1)
	{
		while (i2 != last2)
		{
			pred_mark2(*i2);
			++i2;
		}
		return;
	}
	if (i2 == last2)
	{
		while (i1 != last1)
		{
			pred_mark1(*i1);
			++i1;
		}
		return;
	}
	
	for (;;)
	{
		if (pred_less(*i1, *i2))
		{
			pred_mark1(*i1);
			if (++i1 == last1)
				break;
		}
		else if (pred_less(*i2, *i1))
		{
			pred_mark2(*i2);
			if (++i2 == last2)
				break;
		}
		else
		{
			++i1;
			++i2;
			if (i1 == last1 || i2 == last2)
				break;
		}
	}
	if (i1 == last1)
	{
		while (i2 != last2)
		{
			pred_mark2(*i2);
			++i2;
		}
		return;
	}
	if (i2 == last2)
	{
		while (i1 != last1)
		{
			pred_mark1(*i1);
			++i1;
		}
		return;
	}
}

/*****************************************************************************************
						mark_consecutive_duplicates
******************************************************************************************/
// assumes range sorted
template<typename It, typename PRED_Mark>
inline
unsigned mark_consecutive_duplicates(It beg, It end, PRED_Mark mark)
{
	// ignore empty range
	if (beg == end)
		return 0;

	// two iterators point to successive items
	It i1, i2;
	i1 = i2 = beg;
	i2++;

	unsigned cnt = 0;
	// remember last marked item to handle duplicates at the end of the range
	It last_marked = end;
	while (i2 != end)
	{
		// mark successive duplicates
		if (*i1 == *i2)
		{
			// mark start of new range of duplicates
			if (last_marked != i1)
			{
				cnt++;
				mark(*i1);
			}

			// mark and remember duplicate
			mark(*i2);
			last_marked = i2;
			cnt++;
		}
		++i1;
		++i2;
	}
	return cnt;
}


// assumes range sorted
template<typename It, typename PRED_Mark, typename PRED_EQ>
inline
unsigned mark_consecutive_duplicates(It beg, It end, PRED_EQ pred_eq, PRED_Mark mark)
{
	// ignore empty range
	if (beg == end)
		return 0;

	// two iterators point to successive items
	It i1 = beg;
	It i2 = beg;	++i2;

	unsigned cnt = 0;

	// remember last marked item to handle duplicates at the end of the range
	It last_marked = end;
	while (i2 != end)
	{
		// mark successive duplicates
		if (pred_eq(*i1 == *i2))
		{
			// mark start of new range of duplicates
			if (last_marked != i1)
			{
				mark(*i1);
				cnt++;
			}

			// mark and remember duplicate
			mark(*i2);
			last_marked = i2;
			cnt++;
		}
		++i1;
		++i2;
	}
	return cnt;
}

/*****************************************************************************************
						op_ignore

					do nothing function
******************************************************************************************/
template<typename T> struct op_ignore
{
	void operator ()(const T&)
	{
	}
};

#endif	//STLHELPER_H
